SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Suffix array</title>

</head>

Suffix array

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Suffix array</th></tr><tr><th scope="row" class="infobox-label"><a href="List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data"><a href="Array_data_structure" class="mw-redirect" title="Array data structure">Array</a></td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="#CITEREFManberMyers1990">Manber & Myers (1990)</a></td></tr><tr><th colspan="2" class="infobox-header" style="background:lavender"><a href="Time_complexity" title="Time complexity">Time complexity</a> in <a href="Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><td colspan="2" class="infobox-full-data"><table style="width:100%;border-collapse:collapse;border-spacing:0px 0px;border:none"><tbody><tr style="vertical-align:top"><th scope="col"></th><th scope="col"> Average</th><th scope="col"> Worst case</th></tr><tr style="vertical-align:top"><th scope="row"> Space</th><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></td><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></td></tr><tr style="vertical-align:top"><th scope="row"> Construction</th><td> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

In <a href="Computer_science" title="Computer science">computer science</a>, a suffix array is a sorted <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> of all <a href="Suffix_(computer_science)" class="mw-redirect" title="Suffix (computer science)">suffixes</a> of a <a href="String_(computer_science)" title="String (computer science)">string</a>. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field of <a href="Bibliometrics" title="Bibliometrics">bibliometrics</a>.

Suffix arrays were introduced by <a href="#CITEREFManberMyers1990">Manber & Myers (1990)</a> as a simple, space efficient alternative to <a href="Suffix_tree" title="Suffix tree">suffix trees</a>. They had independently been discovered by <a href="Gaston_Gonnet" title="Gaston Gonnet">Gaston Gonnet</a> in 1987 under the name PAT array (<a href="#CITEREFGonnetBaeza-YatesSnider1992">Gonnet, Baeza-Yates & Snider 1992</a>).

<a href="#CITEREFLiLiHuo2016">Li, Li & Huo (2016)</a> gave the first in-place <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)}</annotation>

</semantics>

</math><img src="./5aeb15c854068604d35a2dd82a925899fafd3690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.822ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)}" loading="lazy"> additional space beyond the input string and the output suffix array.

Enhanced suffix arrays (ESAs) are suffix arrays with additional tables that reproduce the full functionality of suffix trees preserving the same time and memory complexity.<a href="#cite_note-FOOTNOTEAbouelhodaKurtzOhlebusch2004-1">[1]</a>

A sorted array of only some (rather than all) suffixes of a string is called a sparse suffix array.<a href="#cite_note-FOOTNOTEIKärkkäinenKempa2014-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=S[1]S[2]...S[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=S[1]S[2]...S[n]}</annotation>

</semantics>

</math><img src="./7368634286bb954c1f6acb4885bbb21d0b779cda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.798ex; height:2.843ex;" alt="{\displaystyle S=S[1]S[2]...S[n]}" loading="lazy"> be an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle n}</annotation>

</semantics>

</math><img src="./cc6e1f880981346a604257ebcacdef24c0aca2d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}" loading="lazy">-string and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S[i,j]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S[i,j]}</annotation>

</semantics>

</math><img src="./38fe7fdd57ab786563cca51767a3b9717fc63f92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.587ex; height:2.843ex;" alt="{\displaystyle S[i,j]}" loading="lazy"> denote the substring of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> ranging from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> inclusive.

The suffix array <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> is now defined to be an array of integers providing the starting positions of <a href="Suffix_(computer_science)" class="mw-redirect" title="Suffix (computer science)">suffixes</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> in <a href="Lexicographical_order" class="mw-redirect" title="Lexicographical order">lexicographical order</a>. This means, an entry <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[i]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[i]}</annotation>

</semantics>

</math><img src="./2a0d7a8a3371fad84f7032042e8d1e1caf6aa15e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.839ex; height:2.843ex;" alt="{\displaystyle A[i]}" loading="lazy"> contains the starting position of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th smallest suffix in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> and thus for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq n}</annotation>

</semantics>

</math><img src="./abbe58b9b83f8b6ec0da570e2249323a8930ef1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.557ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq n}" loading="lazy">: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S[A[i-1],n]<S[A[i],n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S[A[i-1],n]<S[A[i],n]}</annotation>

</semantics>

</math><img src="./fa1a146c60a150fd6201ad6370e818bdc45f1cb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.223ex; height:2.843ex;" alt="{\displaystyle S[A[i-1],n]<S[A[i],n]}" loading="lazy">.

Each <a href="Suffix_(computer_science)" class="mw-redirect" title="Suffix (computer science)">suffix</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> shows up in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> exactly once. Suffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Consider the text <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

<th scope="row" style="text-align:left;">i

</th>

<td>7

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S[i]}</annotation>

</semantics>

</math><img src="./bcac18d365382145819781be2eb59d84dd8b4496.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.595ex; height:2.843ex;" alt="{\displaystyle S[i]}" loading="lazy">

</th>

<td>$

</td></tr></tbody></table>

The text ends with the special sentinel letter <code>$</code> that is unique and lexicographically smaller than any other character. The text has the following suffixes:

<th align="left">Suffix</th>

<th align="left">i

</th></tr>

<td align="left">banana$</td>

<td align="left">1

</td></tr>

<td align="left">anana$</td>

<td align="left">2

</td></tr>

<td align="left">3

</td></tr>

<td align="left">4

</td></tr>

<td align="left">5

</td></tr>

<td align="left">6

</td></tr>

<td align="left">7

</td></tr></tbody></table>

These suffixes can be sorted in ascending order:

<th align="left">Suffix</th>

<th align="left">i

</th></tr>

<td align="left">7

</td></tr>

<td align="left">6

</td></tr>

<td align="left">4

</td></tr>

<td align="left">anana$</td>

<td align="left">2

</td></tr>

<td align="left">banana$</td>

<td align="left">1

</td></tr>

<td align="left">5

</td></tr>

<td align="left">3

</td></tr></tbody></table>

The suffix array <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

<th scope="row" style="text-align:left;">i =

</th>

<td>7

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[i]}</annotation>

</semantics>

</th>

<td>3

</td></tr></tbody></table>

The suffix array with the suffixes written out vertically underneath for clarity:

<th scope="row" style="text-align:left;">i =

</th>

<td>7

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[i]}</annotation>

</semantics>

</th>

<td>3

</td></tr>

<tr>

<th scope="row" style="text-align:left;">1

</th>

<td>n

</td></tr>

<tr>

<th scope="row" style="text-align:left;">2

</th>

<td>a

</td></tr>

<tr>

<th scope="row" style="text-align:left;">3

</th>

<td>n

</td></tr>

<tr>

<th scope="row" style="text-align:left;">4

</th>

<td>a

</td></tr>

<tr>

<th scope="row" style="text-align:left;">5

</th>

<td>$

</td></tr>

<tr>

<th scope="row" style="text-align:left;">6

</th>

<td>

</td></tr>

<tr>

<th scope="row" style="text-align:left;">7

</th>

<td>

</td></tr></tbody></table>

So for example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[3]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[3]}</annotation>

</semantics>

</math><img src="./fad3f1cbea6f7cb9b43da98cb6c31e0043e47713.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.199ex; height:2.843ex;" alt="{\displaystyle A[3]}" loading="lazy"> contains the value 4, and therefore refers to the suffix starting at position 4 within <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Correspondence_to_suffix_trees">Correspondence to suffix trees</h2></div>

Suffix arrays are closely related to <a href="Suffix_tree" title="Suffix tree">suffix trees</a>:

<ul><li>Suffix arrays can be constructed by performing a <a href="Depth-first_traversal" class="mw-redirect" title="Depth-first traversal">depth-first traversal</a> of a suffix tree. The suffix array corresponds to the leaf-labels given in the order in which these are visited during the traversal, if edges are visited in the lexicographical order of their first character.</li>

<li>A suffix tree can be constructed in linear time by using a combination of suffix array and <a href="LCP_array" title="LCP array">LCP array</a>. For a description of the algorithm, see the <a href="LCP_array#Suffix_tree_construction" title="LCP array">corresponding section</a> in the <a href="LCP_array" title="LCP array">LCP array</a> article.</li></ul>

It has been shown that every suffix tree algorithm can be systematically replaced with an algorithm that uses a suffix array enhanced with additional information (such as the <a href="LCP_array" title="LCP array">LCP array</a>) and solves the same problem in the same time complexity.<a href="#cite_note-FOOTNOTEAbouelhodaKurtzOhlebusch2004-1">[1]</a>

Advantages of suffix arrays over suffix trees include improved space requirements, simpler linear time construction algorithms (e.g., compared to <a href="Ukkonen's_algorithm" title="Ukkonen's algorithm">Ukkonen's algorithm</a>) and improved cache locality.<a href="#cite_note-FOOTNOTEAbouelhodaKurtzOhlebusch2002-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Space_efficiency">Space efficiency</h2></div>

Suffix arrays were introduced by <a href="#CITEREFManberMyers1990">Manber & Myers (1990)</a> in order to improve over the space requirements of <a href="Suffix_tree" title="Suffix tree">suffix trees</a>: Suffix arrays store <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> integers. Assuming an integer requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4}</annotation>

</semantics>

</math><img src="./295b4bf1de7cd3500e740e0f4f0635db22d87b42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 4}" loading="lazy"> bytes, a suffix array requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4n}</annotation>

</semantics>

</math><img src="./42d3d982c0a63d59f04a9ea9aecec75fb107f6a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.557ex; height:2.176ex;" alt="{\displaystyle 4n}" loading="lazy"> bytes in total. This is significantly less than the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 20n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 20n}</annotation>

</semantics>

</math><img src="./3f9ea64e079f0a3871c95d013ad60fba3aecdddf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.72ex; height:2.176ex;" alt="{\displaystyle 20n}" loading="lazy"> bytes which are required by a careful suffix tree implementation.<a href="#cite_note-FOOTNOTEKurtz1999-4">[4]</a>

However, in certain applications, the space requirements of suffix arrays may still be prohibitive. Analyzed in bits, a suffix array requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log n)}</annotation>

</semantics>

</math><img src="./9981ede263cbf28215d3a70bf30f55db41a6e692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.195ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log n)}" loading="lazy"> space, whereas the original text over an alphabet of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> only requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log \sigma )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log \sigma )}</annotation>

</semantics>

</math><img src="./92ec16b663d24328da1ccb87aa0403aae0a52569.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.13ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log \sigma )}" loading="lazy"> bits.

For a human genome with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma =4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma =4}</annotation>

</semantics>

</math><img src="./b0175571ddfca9b707979289129dd7a499a5b25e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.591ex; height:2.176ex;" alt="{\displaystyle \sigma =4}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=3.4\times 10^{9}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=3.4\times 10^{9}}</annotation>

</semantics>

</math><img src="./2043f775ca7a7041e7e566c67a40d080ff76187e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.684ex; height:2.676ex;" alt="{\displaystyle n=3.4\times 10^{9}}" loading="lazy"> the suffix array would therefore occupy about 16 times more memory than the genome itself.

Such discrepancies motivated a trend towards <a href="Compressed_suffix_array" title="Compressed suffix array">compressed suffix arrays</a> and <a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a>-based compressed full-text indices such as the <a href="FM-index" title="FM-index">FM-index</a>. These data structures require only space within the size of the text or even less.

<div class="mw-heading mw-heading2"><h2 id="Construction_algorithms">Construction algorithms</h2></div>

A suffix tree can be built in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> and can be converted into a suffix array by traversing the tree depth-first also in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy">, so there exist algorithms that can build a suffix array in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

A naive approach to construct a suffix array is to use a <a href="Comparison_sort" title="Comparison sort">comparison-based sorting algorithm</a>. These algorithms require <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log n)}</annotation>

</semantics>

</math><img src="./9981ede263cbf28215d3a70bf30f55db41a6e692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.195ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log n)}" loading="lazy"> suffix comparisons, but a suffix comparison runs in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> time, so the overall runtime of this approach is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2}\log n)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2}\log n)}</annotation>

</semantics>

</math><img src="./ff9d8247a11fce04adfd903d817db246a6d3d44b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.249ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2}\log n)}" loading="lazy">.

More advanced algorithms take advantage of the fact that the suffixes to be sorted are not arbitrary strings but related to each other. These algorithms strive to achieve the following goals:<a href="#cite_note-FOOTNOTEPuglisiSmythTurpin2007-5">[5]</a>

<ul><li>minimal asymptotic complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></li>

<li>lightweight in space, meaning little or no working memory beside the text and the suffix array itself is needed</li>

<li>fast in practice</li></ul>

One of the first algorithms to achieve all goals is the SA-IS algorithm of <a href="#CITEREFNongZhangChan2009">Nong, Zhang & Chan (2009)</a>. The algorithm is also rather simple (< 100 <a href="Source_lines_of_code" title="Source lines of code">LOC</a>) and can be enhanced to simultaneously construct the <a href="LCP_array" title="LCP array">LCP array</a>.<a href="#cite_note-FOOTNOTEFischer2011-6">[6]</a> The SA-IS algorithm is one of the fastest known suffix array construction algorithms. A careful implementation by Yuta Mori<a href="#cite_note-7">[7]</a> outperforms most other linear or super-linear construction approaches.

Beside time and space requirements, suffix array construction algorithms are also differentiated by their supported <a href="Alphabet_(computer_science)" class="mw-redirect" title="Alphabet (computer science)">alphabet</a>: constant alphabets where the alphabet size is bound by a constant, integer alphabets where characters are integers in a range depending on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and general alphabets where only character comparisons are allowed.<a href="#cite_note-FOOTNOTEBurkhardtKärkkäinen2003-8">[8]</a>

Most suffix array construction algorithms are based on one of the following approaches:<a href="#cite_note-FOOTNOTEPuglisiSmythTurpin2007-5">[5]</a>

<ul><li>Prefix doubling algorithms are based on a strategy of <a href="#CITEREFKarpMillerRosenberg1972">Karp, Miller & Rosenberg (1972)</a>. The idea is to find prefixes that honor the lexicographic ordering of suffixes. The assessed prefix length doubles in each iteration of the algorithm until a prefix is unique and provides the rank of the associated suffix.</li>

<li>Recursive algorithms follow the approach of the suffix tree construction algorithm by <a href="#CITEREFFarach1997">Farach (1997)</a> to recursively sort a subset of suffixes. This subset is then used to infer a suffix array of the remaining suffixes. Both of these suffix arrays are then merged to compute the final suffix array.</li>

<li>Induced copying algorithms are similar to recursive algorithms in the sense that they use an already sorted subset to induce a fast sort of the remaining suffixes. The difference is that these algorithms favor iteration over recursion to sort the selected suffix subset. A survey of this diverse group of algorithms has been put together by <a href="#CITEREFPuglisiSmythTurpin2007">Puglisi, Smyth & Turpin (2007)</a>.</li></ul>

A well-known recursive algorithm for integer alphabets is the DC3 / skew algorithm of <a href="#CITEREFKärkkäinenSanders2003">Kärkkäinen & Sanders (2003)</a>. It runs in linear time and has successfully been used as the basis for parallel<a href="#cite_note-FOOTNOTEKullaSanders2007-9">[9]</a> and <a href="External_memory_algorithm" title="External memory algorithm">external memory</a><a href="#cite_note-FOOTNOTEDementievKärkkäinenMehnertSanders2008-10">[10]</a> suffix array construction algorithms.

Recent work by <a href="#CITEREFSalsonLecroqLéonardMouchard2010">Salson et al. (2010)</a> proposes an algorithm for updating the suffix array of a text that has been edited instead of rebuilding a new suffix array from scratch. Even if the theoretical worst-case time complexity is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log n)}</annotation>

</semantics>

</math><img src="./9981ede263cbf28215d3a70bf30f55db41a6e692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.195ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log n)}" loading="lazy">, it appears to perform well in practice: experimental results from the authors showed that their implementation of dynamic suffix arrays is generally more efficient than rebuilding when considering the insertion of a reasonable number of letters in the original text.

In practical <a href="Open_source" title="Open source">open source</a> work, a commonly used routine for suffix array construction was qsufsort, based on the 1999 Larsson-Sadakane algorithm.<a href="#cite_note-11">[11]</a> This routine has been superseded by Yuta Mori's DivSufSort, "the fastest known suffix sorting algorithm in main memory" as of 2017. It too can be modified to compute an LCP array. It uses a induced copying combined with Itoh-Tanaka.<a href="#cite_note-12">[12]</a> In 2021 a faster implementation of the algorithm was presented by Ilya Grebnov <a href="#cite_note-13">[13]</a> which in average showed 65% performance improvement over DivSufSort implementation on the <a href="Silesia_corpus" title="Silesia corpus">Silesia corpus</a>.<a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Generalized_suffix_array">Generalized suffix array</h2></div>

The concept of a suffix array can be extended to more than one string. This is called a generalized suffix array (or GSA), a suffix array that contains all suffixes for a set of strings (for example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}</annotation>

</semantics>

</math><img src="./510e5c211d900936d1a79954c45482699b5384f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.786ex; height:2.509ex;" alt="{\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}" loading="lazy"> and is lexicographically sorted with all suffixes of each string.<a href="#cite_note-FOOTNOTEShi1996-15">[15]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

The suffix array of a string can be used as an <a href="Index_(search_engine)" class="mw-redirect" title="Index (search engine)">index</a> to quickly locate every occurrence of a substring pattern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> within the string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy">. Finding every occurrence of the pattern is equivalent to finding every suffix that begins with the substring. Thanks to the lexicographical ordering, these suffixes will be grouped together in the suffix array and can be found efficiently with two <a href="Binary_search" title="Binary search">binary searches</a>. The first search locates the starting position of the interval, and the second one determines the end position:

<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>n = len(S)

def search(P: str) -> tuple[int, int]:

"""

Return indices (s, r) such that the interval A[s:r] (including the end

index) represents all suffixes of S that start with the pattern P.

"""

# Find starting position of interval

l = 0 # in Python, arrays are indexed starting at 0

r = n

while l < r:

mid = (l + r) // 2 # division rounding down to nearest integer

# suffixAt(A[i]) is the ith smallest suffix

if P > suffixAt(A[mid]):

l = mid + 1

else:

r = mid

s = l

# Find ending position of interval

r = n

while l < r:

if suffixAt(A[mid]).startswith(P):

l = mid + 1

else:

r = mid

return (s, r)

</pre></div>

Finding the substring pattern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> in the string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(m\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(m\log n)}</annotation>

</semantics>

</math><img src="./4c8701e5543dcc0eced4426296c6d67db31db5bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.84ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(m\log n)}" loading="lazy"> time, given that a single suffix comparison needs to compare <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> characters. <a href="#CITEREFManberMyers1990">Manber & Myers (1990)</a> describe how this bound can be improved to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(m+\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(m+\log n)}</annotation>

</semantics>

</math><img src="./c33048ecbc367c7aa852f6e354e69f48844b5ac1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.294ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(m+\log n)}" loading="lazy"> time using <a href="LCP_array" title="LCP array">LCP</a> information. The idea is that a pattern comparison does not need to re-compare certain characters, when it is already known that these are part of the longest common prefix of the pattern and the current search interval. <a href="#CITEREFAbouelhodaKurtzOhlebusch2004">Abouelhoda, Kurtz & Ohlebusch (2004)</a> improve the bound even further and achieve a search time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(m)}</annotation>

</semantics>

</math><img src="./089694843af30c69c8b1d6287c3d8f0e2868499c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.7ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(m)}" loading="lazy"> for constant alphabet size, as known from <a href="Suffix_tree" title="Suffix tree">suffix trees</a>.

Suffix sorting algorithms can be used to compute the <a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">Burrows–Wheeler transform (BWT)</a>. The <a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a> requires sorting of all cyclic permutations of a string. If this string ends in a special end-of-string character that is lexicographically smaller than all other character (i.e., $), then the order of the sorted rotated <a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a> matrix corresponds to the order of suffixes in a suffix array. The <a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a> can therefore be computed in linear time by first constructing a suffix array of the text and then deducing the <a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a> string: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BWT[i]=S[A[i]-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BWT[i]=S[A[i]-1]}</annotation>

</semantics>

</math><img src="./a461b668e8ffa1c9fcf4dff9aae56e57bdbd1937.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.665ex; height:2.843ex;" alt="{\displaystyle BWT[i]=S[A[i]-1]}" loading="lazy">.

Suffix arrays can also be used to look up substrings in <a href="Example-based_machine_translation" title="Example-based machine translation">example-based machine translation</a>, demanding much less storage than a full phrase table as used in <a href="Statistical_machine_translation" title="Statistical machine translation">Statistical machine translation</a>.

Many additional applications of the suffix array require the <a href="LCP_array" title="LCP array">LCP array</a>. Some of these are detailed in the <a href="LCP_array#Applications" title="LCP array">application section</a> of the latter.

<div class="mw-heading mw-heading2"><h2 id="Enhanced_suffix_arrays">Enhanced suffix arrays</h2></div>

Suffix trees are powerful data structures that have wide application in areas of pattern and string matching, indexing and textual statistics. However, it occupies a significant amount of space and thus has a drawback in many real-time applications that require processing a considerably large amount of data like genome analysis. To overcome this drawback, Enhanced Suffix Arrays were developed that are data structures consisting of suffix arrays and an additional table called the child table that contains the information about the parent-child relationship between the nodes in the suffix tree. The node branching data structure for this tree is a linked list. Enhanced suffix arrays are superior in terms of both space efficiency and time complexity and are easy to implement. Moreover, they can be applied to any algorithm that uses a suffix tree by using an abstract concept lcp-interval trees. The time complexity for searching a pattern in an enhanced suffix array is O(m|Σ|).

The suffix array of the string is an array of n integers in the range of 0 to n that represents the n+1 suffixes of the string including the special character #.

The suffix array is composed of two arrays:

<ol><li>pos array pos[1,...n]: It represents a sorted list of all S suffixes. Only the initial positions of the suffixes are stored in the array to reduce the space complexity since the suffixes are too large.</li>

<li>lcp array lcp[1,...n]: It is an array of n integers that maintains the lengths of the longest common prefix of two consecutive suffixes stored in the pos array.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Constructing_the_lcp-interval">Constructing the lcp-interval</h2></div>

For a suffix array of S, the lcp-interval associated with the corresponding node of suffix tree of S can be defined as:

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">Interval [i,..j], 0 ≤ i ≤ j ≤ n is an lcp-interval of lcp-value, if

<ol><li>lcptab[i] < l,</li>

<li>lcptab[k] ≥ l for all i + 1 ≤ k ≤ j,</li>

<li>lcptab[k] = l for some i + 1 ≤ k ≤ j if i ≠ j and l = n − i + 1 if i = j,</li>

<li>lcptab[j + 1] < l.</li></ol></blockquote>

The length of the longest common prefix of pos[i − 1] and pos[i] is stored in lcp[i],where 2 ≤ i ≤ n. The lcp-interval portrays the same parent-child relationship as that among the associated nodes in the suffix tree of S.This shows that if the corresponding node of [i..j] is a child of the corresponding node of [k..l], a lcp-interval [i..j] is a child interval of another lcp-interval [k..l]. If [k..l] is a child interval of [i..j], a lcp-interval [i..j] is the parent interval of a lcp-interval [k..l].

<div class="mw-heading mw-heading2"><h2 id="Constructing_a_child_table">Constructing a child table</h2></div>

The child table cldtab is composed of three n arrays, up, down and nextlIndex. The information about the edges of the corresponding suffix tree is stored and maintained by the up and down arrays. The nextlIndex array stores the links in the linked list used for node branching the suffix tree.

The up, down and nextlIndex array are defined as follows:

<ol><li>The element up[i] records the starting index of the longest lcp-second interval’s child interval, which ends at index i-1.</li>

<li>The initial index of the second child interval of the longest lcp-interval, starting at index i is stored in the element down[i].</li>

<li>If and only if the interval is neither the first child nor the final child of its parent, the element nextlIndex[i] contains the first index of the next sibling interval of the longest lcp-interval, starting at index i.</li></ol>

By performing a bottom-up traversal of the lcp-interval of the tree, the child table can be constructed in linear time. The up/down values and the nextlIndex values can be computed separately by using two distinct algorithms.

<div class="mw-heading mw-heading2"><h2 id="Constructing_a_suffix_link_table">Constructing a suffix link table</h2></div>

The suffix links for an enhanced suffix array can be computed by generating the suffix link interval [1,..,r] for each [i,..j] interval during the preprocessing. The left and right elements l and r of the interval are maintained in the first index of [i,..,j]. The table for this interval ranges from 0 to n. The suffix link table is constructed by the left-to-right breadth-first traversal of the lcp-interval tree. Every time an l-interval is computed, it is added to the list of l-intervals, which is referred to as the l-list. When the lcp-value > 0, for every l-interval[i,..,j] in the list, link[i] is calculated. The interval [l,..,r] is computed by a binary search in(l-1)-list, where l is the largest left boundary amongst all the l-1 intervals. The suffix link interval of [i,..j] is represented by this interval[l,..,r]. The values l and r are ultimately stored in the first index of [i,..,j].

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-FOOTNOTEAbouelhodaKurtzOhlebusch2004-1">^ <a href="#cite_ref-FOOTNOTEAbouelhodaKurtzOhlebusch2004_1-0">a</a> <a href="#cite_ref-FOOTNOTEAbouelhodaKurtzOhlebusch2004_1-1">b</a> <a href="#CITEREFAbouelhodaKurtzOhlebusch2004">Abouelhoda, Kurtz & Ohlebusch 2004</a>.

</li>

<li id="cite_note-FOOTNOTEIKärkkäinenKempa2014-2"><a href="#cite_ref-FOOTNOTEIKärkkäinenKempa2014_2-0">^</a> <a href="#CITEREFIKärkkäinenKempa2014">I, Kärkkäinen & Kempa 2014</a>.

</li>

<li id="cite_note-FOOTNOTEAbouelhodaKurtzOhlebusch2002-3"><a href="#cite_ref-FOOTNOTEAbouelhodaKurtzOhlebusch2002_3-0">^</a> <a href="#CITEREFAbouelhodaKurtzOhlebusch2002">Abouelhoda, Kurtz & Ohlebusch 2002</a>.

</li>

<li id="cite_note-FOOTNOTEKurtz1999-4"><a href="#cite_ref-FOOTNOTEKurtz1999_4-0">^</a> <a href="#CITEREFKurtz1999">Kurtz 1999</a>.

</li>

<li id="cite_note-FOOTNOTEPuglisiSmythTurpin2007-5">^ <a href="#cite_ref-FOOTNOTEPuglisiSmythTurpin2007_5-0">a</a> <a href="#cite_ref-FOOTNOTEPuglisiSmythTurpin2007_5-1">b</a> <a href="#CITEREFPuglisiSmythTurpin2007">Puglisi, Smyth & Turpin 2007</a>.

</li>

<li id="cite_note-FOOTNOTEFischer2011-6"><a href="#cite_ref-FOOTNOTEFischer2011_6-0">^</a> <a href="#CITEREFFischer2011">Fischer 2011</a>.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMori" class="citation web cs1">Mori, Yuta. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230309123010/https://sites.google.com/site/yuta256/sais">"sais"</a>. Archived from <a rel="nofollow" class="external text" href="https://sites.google.com/site/yuta256/sais">the original</a> on 9 Mar 2023. Retrieved 31 Aug 2023.</cite>

</li>

<li id="cite_note-FOOTNOTEBurkhardtKärkkäinen2003-8"><a href="#cite_ref-FOOTNOTEBurkhardtKärkkäinen2003_8-0">^</a> <a href="#CITEREFBurkhardtKärkkäinen2003">Burkhardt & Kärkkäinen 2003</a>.

</li>

<li id="cite_note-FOOTNOTEKullaSanders2007-9"><a href="#cite_ref-FOOTNOTEKullaSanders2007_9-0">^</a> <a href="#CITEREFKullaSanders2007">Kulla & Sanders 2007</a>.

</li>

<li id="cite_note-FOOTNOTEDementievKärkkäinenMehnertSanders2008-10"><a href="#cite_ref-FOOTNOTEDementievKärkkäinenMehnertSanders2008_10-0">^</a> <a href="#CITEREFDementievKärkkäinenMehnertSanders2008">Dementiev et al. 2008</a>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFLarssonSadakane2007" class="citation journal cs1">Larsson, N. Jesper; Sadakane, Kunihiko (22 November 2007). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2007.07.017">"Faster suffix sorting"</a>. Theoretical Computer Science. 387 (3): 258–272. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2007.07.017">10.1016/j.tcs.2007.07.017</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0304-3975">0304-3975</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFFischerKurpicz2017" class="citation journal cs1">Fischer, Johannes; Kurpicz, Florian (5 October 2017). "Dismantling DivSufSort". Proceedings of the Prague Stringology Conference 2017. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1710.01896">1710.01896</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://encode.su/threads/3579-New-saca-and-bwt-library-(libsais)">"New saca and bwt library (libsais)"</a>. encode.su. Retrieved 2021-10-03.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFGrebnov2021" class="citation cs2">Grebnov, Ilya (2021-09-22), <a rel="nofollow" class="external text" href="https://github.com/IlyaGrebnov/libsais">libsais</a>, retrieved 2021-10-02</cite>

</li>

<li id="cite_note-FOOTNOTEShi1996-15"><a href="#cite_ref-FOOTNOTEShi1996_15-0">^</a> <a href="#CITEREFShi1996">Shi 1996</a>.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFManberMyers1990" class="citation conference cs1"><a href="Udi_Manber" title="Udi Manber">Manber, Udi</a>; <a href="Gene_Myers" class="mw-redirect" title="Gene Myers">Myers, Gene</a> (1990). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=320176.320218">Suffix arrays: a new method for on-line string searches</a>. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.</cite></li>

<li><cite id="CITEREFManberMyers1993" class="citation journal cs1"><a href="Udi_Manber" title="Udi Manber">Manber, Udi</a>; <a href="Gene_Myers" class="mw-redirect" title="Gene Myers">Myers, Gene</a> (1993). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=320176.320218">"Suffix arrays: a new method for on-line string searches"</a>. SIAM Journal on Computing. 22 (5): 935–948. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0222058">10.1137/0222058</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5074629">5074629</a>.</cite></li>

<li><cite id="CITEREFLiLiHuo2016" class="citation conference cs1">Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimal In-Place Suffix Sorting. Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science. Vol. 11147. Springer. pp. 268–284. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1610.08305">1610.08305</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-00479-8_22">10.1007/978-3-030-00479-8_22</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-00478-1</bdi>.</cite></li>

<li><cite id="CITEREFShi1996" class="citation conference cs1">Shi, Fei (1996). "Suffix arrays for multiple strings: A method for on-line multiple string searches". Concurrency and Parallelism, Programming, Networking, and Security. Lecture Notes in Computer Science. Vol. 1179. Springer Berlin Heidelberg. pp. 11–22. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0027775">10.1007/BFb0027775</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-62031-0</bdi>.</cite></li>

<li><cite id="CITEREFAbouelhodaKurtzOhlebusch2002" class="citation conference cs1">Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array and Its Applications to Genome Analysis. Algorithms in Bioinformatics. <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>. Vol. 2452. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45784-4_35">10.1007/3-540-45784-4_35</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-44211-0</bdi>.</cite></li>

<li><cite id="CITEREFAbouelhodaKurtzOhlebusch2004" class="citation journal cs1">Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (March 2004). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS1570-8667%2803%2900065-0">"Replacing suffix trees with enhanced suffix arrays"</a>. Journal of Discrete Algorithms. 2 (1): 53–86. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS1570-8667%2803%2900065-0">10.1016/S1570-8667(03)00065-0</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1570-8667">1570-8667</a>.</cite></li>

<li><cite id="CITEREFGonnetBaeza-YatesSnider1992" class="citation journal cs1">Gonnet, G.H.; Baeza-Yates, R.A.; Snider, T. (1992). <a rel="nofollow" class="external text" href="http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap05.htm">"New indices for text: PAT trees and PAT arrays"</a>. Information Retrieval: Data Structures and Algorithms.</cite></li>

<li><cite id="CITEREFKurtz1999" class="citation journal cs1">Kurtz, S (1999). "Reducing the space requirement of suffix trees". Software: Practice and Experience. 29 (13): 1149–1171. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2F%28SICI%291097-024X%28199911%2929%3A13%3C1149%3A%3AAID-SPE274%3E3.0.CO%3B2-O">10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10338.dmlcz%2F135448">10338.dmlcz/135448</a>.</cite></li>

<li><cite id="CITEREFPuglisiSmythTurpin2007" class="citation journal cs1">Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). <a rel="nofollow" class="external text" href="http://researchrepository.murdoch.edu.au/id/eprint/27889/">"A taxonomy of suffix array construction algorithms"</a>. ACM Computing Surveys. 39 (2): 4. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1242471.1242472">10.1145/1242471.1242472</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2653529">2653529</a>.</cite></li>

<li><cite id="CITEREFNongZhangChan2009" class="citation conference cs1">Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linear Suffix Array Construction by Almost Pure Induced-Sorting. 2009 Data Compression Conference. p. 193. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FDCC.2009.42">10.1109/DCC.2009.42</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-3592-0</bdi>.</cite></li>

<li><cite id="CITEREFFischer2011" class="citation conference cs1">Fischer, Johannes (2011). Inducing the LCP-Array. Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 6844. pp. 374–385. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1101.3448">1101.3448</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-22300-6_32">10.1007/978-3-642-22300-6_32</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-22299-3</bdi>.</cite></li>

<li><cite id="CITEREFSalsonLecroqLéonardMouchard2010" class="citation journal cs1">Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jda.2009.02.007">"Dynamic extended suffix arrays"</a>. Journal of Discrete Algorithms. 8 (2): 241. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jda.2009.02.007">10.1016/j.jda.2009.02.007</a>.</cite></li>

<li><cite id="CITEREFBurkhardtKärkkäinen2003" class="citation conference cs1">Burkhardt, Stefan; Kärkkäinen, Juha (2003). Fast Lightweight Suffix Array Construction and Checking. Combinatorial Pattern Matching. Lecture Notes in Computer Science. Vol. 2676. pp. 55–69. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-44888-8_5">10.1007/3-540-44888-8_5</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-40311-1</bdi>.</cite></li>

<li><cite id="CITEREFKarpMillerRosenberg1972" class="citation conference cs1">Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). Rapid identification of repeated patterns in strings, trees and arrays. Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. pp. 125–136. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800152.804905">10.1145/800152.804905</a>.</cite></li>

<li><cite id="CITEREFFarach1997" class="citation conference cs1">Farach, M. (1997). Optimal suffix tree construction with large alphabets. Proceedings 38th Annual Symposium on Foundations of Computer Science. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1997.646102">10.1109/SFCS.1997.646102</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8186-8197-7</bdi>.</cite></li>

<li><cite id="CITEREFIKärkkäinenKempa2014" class="citation conference cs1">I, Tomohiro; Kärkkäinen, Juha; Kempa, Dominik (2014). Faster Sparse Suffix Sorting. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 25. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. pp. 386–396. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.STACS.2014.386">10.4230/LIPIcs.STACS.2014.386</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-939897-65-1</bdi>.</cite></li>

<li><cite id="CITEREFKärkkäinenSanders2003" class="citation conference cs1">Kärkkäinen, Juha; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, Peter</a> (2003). Simple Linear Work Suffix Array Construction. Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2719. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45061-0_73">10.1007/3-540-45061-0_73</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-40493-4</bdi>.</cite></li>

<li><cite id="CITEREFDementievKärkkäinenMehnertSanders2008" class="citation journal cs1">Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, Peter</a> (2008). <a rel="nofollow" class="external text" href="https://publikationen.bibliothek.kit.edu/1000009446">"Better external memory suffix array construction"</a>. Journal of Experimental Algorithmics. 12: 1–24. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1227161.1402296">10.1145/1227161.1402296</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12296500">12296500</a>.</cite></li>

<li><cite id="CITEREFKullaSanders2007" class="citation journal cs1">Kulla, Fabian; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, Peter</a> (2007). "Scalable parallel suffix array construction". Parallel Computing. 33 (9): 605–612. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.parco.2007.06.004">10.1016/j.parco.2007.06.004</a>.</cite></li>

<li>Mohamed Ibrahim Abouelhoda, Stefan Kurtz, and Enno Ohlebusch. "Replacing suffix trees with enhanced suffix arrays." Journal of Discrete Algorithms, 2(1):53–86, 2004.</li>

<li>Dong Kyue Kim, Jeong Eun Jeon, and Heejin Park. "An efficient index data structure with the capabilities of suffix trees and suffix arrays for alphabets of non-negligible size." String Processing and Information Retrieval Lecture Notes in Computer Science, page138–149, 2004.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Suffix_array" class="extiw external" title="commons:Category:Suffix array">Suffix array</a>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html">Suffix Array in Java</a></li>

<li><a rel="nofollow" class="external text" href="https://code.google.com/p/compression-code/downloads/list">Suffix sorting module for BWT in C code</a></li>

<li><a rel="nofollow" class="external text" href="http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845">Suffix Array Implementation in Ruby</a></li>

<li><a rel="nofollow" class="external text" href="http://sary.sourceforge.net/index.html.en">Suffix array library and tools</a></li>

<li><a rel="nofollow" class="external text" href="http://pizzachili.dcc.uchile.cl/">Project containing various Suffix Array c/c++ Implementations with a unified interface</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/y-256/libdivsufsort">A fast, lightweight, and robust C API library to construct the suffix array</a></li>

<li><a rel="nofollow" class="external text" href="https://code.google.com/p/pysuffix/">Suffix Array implementation in Python</a></li>

<li><a rel="nofollow" class="external text" href="http://www.geeksforgeeks.org/suffix-tree-application-4-build-linear-time-suffix-array/">Linear Time Suffix Array implementation in C using suffix tree</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Strings176" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Strings176" style="font-size:114%;margin:0 4em"><a href="String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li>

<li><a href="Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li>

<li><a href="Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li>

<li><a href="Edit_distance" title="Edit distance">Edit distance</a></li>

<li><a href="Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li>

<li><a href="Hamming_distance" title="Hamming distance">Hamming distance</a></li>

<li><a href="Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li>

<li><a href="Lee_distance" title="Lee distance">Lee distance</a></li>

<li><a href="Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li>

<li><a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>

<li><a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li>

<li><a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li>

<li><a href="Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li>

<li><a href="Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li>

<li><a href="Trigram_search" title="Trigram search">Trigram search</a></li>

<li><a href="Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li>

<li><a href="Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li>

<li><a href="Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular grammar</a></li>

<li><a href="Thompson's_construction" title="Thompson's construction">Thompson's construction</a></li>

<li><a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li>

<li><a href="Hirschberg's_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li>

<li><a href="Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li>

<li><a href="Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li>

<li><a href="Substring_index" title="Substring index">Substring index</a>

<ul>

<li><a href="Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix tree</a></li>

<li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="LCP_array" title="LCP array">LCP array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parsing" title="Parsing">Parsing</a></li>

<li><a href="Pattern_matching" title="Pattern matching">Pattern matching</a></li>

<li><a href="Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li>

<li><a href="Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li>

<li><a href="Longest_common_substring" title="Longest common substring">Longest common substring</a></li>

<li><a href="Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li>

<li>Sorting</li>

<li><a href="Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li>

<li><a href="String_operations" title="String operations">String operations</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-23" href="https://en.wikipedia.org/wiki/?title=Suffix_array&oldid=1287002172">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>